#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxSize 20

typedef struct
{
    char *ch;
    int length;
} Str;

void getnextval(Str substr, int nextval[])
{
    // next数组从下标1位置开始存储
    int j = 1, t = 0;
    nextval[1] = 0;
    while (j < substr.length)
    {
        if (t == 0 || substr.ch[j] == substr.ch[t])
        {
            ++t;
            ++j;
            if (substr.ch[j] != substr.ch[t])
            {
                nextval[j] = t;
            }
            else
            {
                nextval[j] = nextval[t];
            }
        }
        else
        {
            t = nextval[t];
        }
    }
}

int KMP(Str str, Str substr, int next[])
{
    int i = 1, j = 1;
    while (i <= str.length && j <= substr.length)
    {
        if (j == 0 || str.ch[i] == substr.ch[j])
        {
            ++i;
            ++j;
        }
        else
            j = next[j];
    }
    if (j > substr.length)
        return i - substr.length;
    else
        return 0;
}

int main()
{
    int nextval[maxSize];
    Str str;
    Str substr;
    // 初始化str
    str.length = 13;
    substr.length = 9;
    str.ch = (char *)malloc(sizeof(char) * 15);
    substr.ch = (char *)malloc(sizeof(char) * 7);
    // 因为从下标从1开始，所以前面随便填充了一个1
    strcpy(str.ch, "1ABCAABABAAB");
    strcpy(substr.ch, "1ABABAAB");
    getnextval(substr, nextval);
    for (int i = 1; i < substr.length - 1; i++)
    {
        printf("%d,", nextval[i]);
    }
    int m = KMP(str, substr, nextval);
    printf("\n");
    printf("found %d\n", m);
    return 0;
}